UNIX V6 源码分析笔记

Table of Contents

UNIX V6 源码可以在这里获得：https://github.com/dspinellis/unix-history-repo/tree/Research-V6-Snapshot-Development

1. UNIX V6 核心功能

  • 块设备和字符设备
  • 系统调用
  • 进程管理：进程调度、进程创建
  • 文件系统
  • 交换空间
  • 系统初始化：启动、进程初始化
  • 多用户
  • 中断处理
  • shell
  • 管道

2. PDP-11/40 基本知识

UNIBUS 总线将各个部件连接在一起，如下结构： 

<====================UNIBUS====================>
      |      |        |        |
  +-----+ +-----+  +------+ +-----+
  | CPU | | 内存 |  | I/O |  | I/O |  ....
  +-----+ +-----+  +------+ +-----+

这样每个 I/O 的寄存器就可以映射到内存地址，通过访问内存来读写 I/O。比如可以直接读写内存地址来操作 CPU 的寄存器。

UNIBUS 的地址总线宽度为 18bit。内存的最高位的 8KB 空间用来映射 I/O 寄存器。

2.1. 寄存器

7 个通用寄存器，r0 ～ r7。其中 r6 有两个，分别在内核空间和用户空间，在切换模式时，r6 也会跟真切换。通用寄存器大小 8KB。

各寄存器含义如下：

寄存器 说明
r0,r1 存储运和函数的返回值
r2,r3,r4 本地处理（就是程序自由使用）
r5 帧指针
r6 SP，栈指针，硬件层面上，用户模式和内核模式各有一个
r7 PC，程序计数器

PSW 寄存器：处理器状态字寄存器，宽度为 16 位。

比特位说明：

比特位 说明
0 借位位，借位时值为 1
1 溢出位，溢出时值为 1
2 零位，指令执行结果为 0 时，这里置为 1
3 负位，指令执行结果为负时，这里置为 1
4 陷入（trap）
5～7 处理器优先级，取值范围：0～7
8～11 无用途
12～13 处理器先前模式
14～15 处理器当前模式

其中 0～3 位为条件码，12～15 位为模式位，00 表示内核模式，11 表示用户模式。

PSW 寄存器映射到内存地址 0177776，定义在 V6 源码中： 

#define PS 0177776

3. 进程

所有进程都保存在全局数组 proc 中，每个元素都是一个 proc 结构体类型。定义如下： 

struct proc
{
char p_stat;
char p_flag;
char p_pri; /* priority, negative is high */
char p_sig; /* signal number sent to this process */
char p_uid; /* user id, used to direct tty signals */
char p_time; /* resident time for scheduling */
char p_cpu; /* cpu usage for scheduling */
char p_nice; /* nice for scheduling */
int p_ttyp; /* controlling tty */
int p_pid; /* unique process id */
int p_ppid; /* process id of parent */
int p_addr; /* address of swappable image */
int p_size; /* size of swappable image (*64 bytes) */
int p_wchan; /* event process is awaiting */
int *p_textp; /* pointer to text structure */
} proc[NPROC];

proc 结构体保存了进程信息，比如 PID、UID 等等。

其中 NPROC 定义了系统最多的进程数： 

#define NPROC 50 /* max number of processes */

另一个结构体是 user，用来保存进程资源占用的信息： 

struct user
{
  int u_rsav[2]; /* 进程切换时保存 r5 和 r6 寄存器的值 */
  int u_fsav[25]; /* save fp registers */
  /* rsav and fsav must be first
   * in structure
   * PDP-11/40不用 */
  char u_segflg; /* flag for IO; user or kernel space */
  char u_error; /* 出错时保存状态码 */
  char u_uid; /* 实效 UID */
  char u_gid; /* 实效 GID */
  char u_ruid; /* 实际 UID */
  char u_rgid; /* 实际 GID */
  int u_procp; /* 指向 proc[] 元素 */
  char *u_base; /* base address for IO */
  char *u_count; /* bytes remaining for IO */
  char *u_offset[2]; /* offset in file for IO */
  int *u_cdir; /* pointer to inode of current directory */
  char u_dbuf[DIRSIZ]; /* current pathname component */
  char *u_dirp; /* current pointer to inode */
  struct { /* 当前目录 */
    int u_ino;
    char u_name[DIRSIZ]; /* 目录名 */
  } u_dent;
  int *u_pdir; /* inode of parent directory of dirp */
  int u_uisa[16]; /* prototype of segmentation addresses */
  int u_uisd[16]; /* prototype of segmentation descriptors */
  int u_ofile[NOFILE]; /* pointers to file structures of open files */
  int u_arg[5]; /* arguments to current system call */
  int u_tsize; /* 代码段大小 (*64) */
  int u_dsize; /* 数据段大小 (*64) */
  int u_ssize; /* 栈大小 (*64) */
  int u_sep; /* flag for I and D separation */
  int u_qsav[2]; /* label variable for quits and interrupts */
  int u_ssav[2]; /* label variable for swapping */
  int u_signal[NSIG]; /* disposition of signals */
  int u_utime; /* 用户模式下 CPU 滴答数 */
  int u_stime; /* 内核模式下 CPU 滴答数 */
  int u_cutime[2]; /* sum of childs' utimes */
  int u_cstime[2]; /* sum of childs' stimes */
  int *u_ar0; /* address of users saved R0 */
  int u_prof[4]; /* profile arguments */
  char u_intflg; /* catch intr from sys */
  /* kernel stack per user
   * extends from u + USIZE*64
   * backward not to reach here
   */
} u;

user 结构体由全局变量 u 表示。

3.1. 进程状态

V6 的进程大体上有两个状态：可执行和休眠。

状态定义如下： 

#define SSLEEP 1 /* 高优先级休眠 */
#define SWAIT 2 /* 低优先级休眠 */
#define SRUN 3 /* 可执行状态 */
#define SIDL 4 /* 进程生成中 */
#define SZOMB 5 /* 僵尸 */
#define SSTOP 6 /* 能够被跟踪（trace） */

proc 结构体的 p_flag 定义了进程的标志常量： 

#define SLOAD 01 /* 处于内存中 */
#define SSYS 02 /* 系统进程，不会被 swap 出去，UNIX V6 只有 proc[0] */
#define SLOCK 04 /* 调度锁，锁住后不让进程被 swap 出去 */
#define SSWAP 010 /* 进程已经被 swap 出去 */
#define STRC 020 /* 进程处于被跟踪（trace）状态 */
#define SWTED 040 /* 跟踪时使用的另一个状态 */

3.2. 内存分配

进程分代码段和数据段。

代码段由数组 text[] 管理，进程代码段的长度由 user.u_tsize 表示。

由于多个相同代码的进程可以共享一个代码段，所以 text[] 是全局的。text 结构体定义如下： 

/* V6 实现了内存共享，因为代码段的内容是不可变的，
 * 所以 text 是全局变量，如果存在多个执行文件副本，在内存
 * 中是共享一份 */
struct text
{
        int     x_daddr;        /* 磁盘中的地址 disk address of segment */
        int     x_caddr;        /* 读入内存后的物理地址 core address, if loaded */
        int     x_size;         /* 代码段长度，以 64 字节为分块单位 size (*64) */
        int     *x_iptr;        /* inode中对应文件的指针 inode of prototype */
        char    x_count;        /* 所有进程对它的引用计数 reference count */
        char    x_ccount;       /* 内存中进程的引用计数 number of loaded references */
} text[NTEXT]; /* NTEXT 为 40 */

数据段大小保存在 proc.p_size 中。段包含了 3 个区域：内核栈、用户模式的数据区域和用户模式的栈区域。proc.p_size 包含了 3 个段的大小：

  • proc.p_addr：指向内核栈区域起始，即 PPDA（Per Process Data Area），范围又 USIZE 定义：
#define USIZE 16 /* size of user block (*64) */
  • user.u_dsize：数据区（静态变量、堆区域等）大小
  • user.u_ssize：栈大小

3.3. 虚拟地址

每个进程拥有长度 16 位（64KB）的虚拟地址空间。通过 MMU 把 16 位虚拟地址转换成 18 位物理地址。物理地址大小：256KB。使用虚拟地址的目的是为了不让程序直接访问物理内存，因为要访问的物理内存可能是其他进程在使用，使用虚拟地址就不需要程序去关注物理内存的管理，保证了独立性。

3.4. 物理地址转换

MMU 有两个寄存器，SR0 和 SR2，SR0 保存出错信息和内存有效的标志位；SR2 保存 16 位虚拟地址。MMU 通过 APR（Active Page Register）寄存器完成虚拟地址到物理地址转换；APR 由 PAR（Page Address Register）和 PDR（Page Description Register）组成。

PAR 定义如下：

0～11 基地址

PDR 定义如下：

1～2 页的访问控制方法。00：未分配；01：只读；11：只写
3 为 1 时，页按高地址向低地址的方向匹配
6 表示页是否更新
8～14 页的块数

APR 一共有 8 组（0～7），虚拟地址空间以页为单位。1 组 APR 对应 1 页，每页最多 128个块（8KB）。

虚拟地址寻址过程：

虚拟地址的高 3 位决定了页（APR），PAR 的基地址+虚拟地址 12～6bit 得到物理内存的块地址，再加上虚拟地址 5～0 位（块偏移地址），得到物理地址。

3.5. 创建进程

UNIX 进程是一个树状关系，创建一个新的进程为子进程，原进程为子进程的父进程，子进程继承了父进程的数据，比如打开的文件等等。

通过系统调用 fork 创建进程，父进程调用 wait 等待子进程执行完毕。子进程调用 exec 把程序载入内存执行。子进程结束后调用 exit。

进程保存在 proc 数组中。

全局变量 mpid 用来保存 PID： 

int mpid; /* generic for unique process id's */

3.5.1. fork

fork 是一个系统调用，用来创建一个新进程，最终工作的函数是 newproc，它主要完成几个工作：

  • 在 proc 数组中找出空位置
  • 生成一个新的 PID
  • 复制父进程的数据，并为子进程分配空间

过程：

在用户模式下调用 C 语言的 fork 函数，首先调用系统中断： 

sys fork

然后调用内核里的 fork 函数： 

/*
 * fork system call.
 */
fork()
{
        register struct proc *p1, *p2;

        /* u 当前是父进程的数据 */
        p1 = u.u_procp;
        /* 在 proc 中寻找空位 */
        for(p2 = &proc[0]; p2 < &proc[NPROC]; p2++)
                if(p2->p_stat == NULL)
                        goto found;
        u.u_error = EAGAIN;
        goto out;

found:
   /* 注意 newproc 返回给父进程的值为 0
     * 所以这里 if 判断为 false
     * 但是子进程返回的是 1，所以执行逻辑体中代码 */
        if(newproc()) {
                    /* 子进程的返回值设置为父进程的 PID */
                u.u_ar0[R0] = p1->p_pid;
                u.u_cstime[0] = 0;
                u.u_cstime[1] = 0;
                u.u_stime = 0;
                u.u_cutime[0] = 0;
                u.u_cutime[1] = 0;
                u.u_utime = 0;
                return;
        }

        /* 把 p_pid 放到 r0 寄存器中，r0 存储返回值，这是给父进程的 */
        u.u_ar0[R0] = p2->p_pid;

out:
        /* r7 保存的是计数器，移动到下条指令 */
        u.u_ar0[R7] =+ 2;
}

fork 函数最终让子进程调用 newproc 函数完成进程创建： 

newproc()
{
        int a1, a2;
        struct proc *p, *up;
        register struct proc *rpp;
        register *rip, n;

        p = NULL;
        /*
         * First, just locate a slot for a process
         * and copy the useful info from this process into it.
         * The panic "cannot happen" because fork has already
         * checked for the existence of a slot.
         */
retry:
        /* 生成新进程的 PID */
        mpid++;
        /* 如果 PID 的值超出整型范围，就从 0 开始 */
        if(mpid < 0) {
                mpid = 0;
                /* 因为 PID 0 是系统进程，所以不能为 0 */
                goto retry;
        }
        /* 从 proc 数组中找出未分配的进程信息 */
        for(rpp = &proc[0]; rpp < &proc[NPROC]; rpp++) {
                /* proc.p_stat 为 NULL，表示可用 */
                if(rpp->p_stat == NULL && p==NULL)
                        p = rpp;
                /* 说明 PID 被占用了 */
                if (rpp->p_pid==mpid)
                        goto retry;
        }
        if ((rpp = p)==NULL)
                panic("no procs");

        /*
         * make proc entry for new proc
         */

        /* 把父进程的信息拷贝给子进程 */
        rip = u.u_procp;
        up = rip;
        rpp->p_stat = SRUN; /* 标记成可运行，进程调度器就可以让它创建
                               之后执行了 */
        rpp->p_flag = SLOAD; /* 表示数据处于内存中，而不是 swap 出去了 */
        rpp->p_uid = rip->p_uid;
        rpp->p_ttyp = rip->p_ttyp;
        rpp->p_nice = rip->p_nice;
        rpp->p_textp = rip->p_textp; /* 拷贝代码区 */
        rpp->p_pid = mpid; /* 上面做了很多事就是生成 PID
                            * 生成 PID 其实可以独立成一个函数？ */
        rpp->p_ppid = rip->p_pid; /* 父进程 PID 就是当前进程 */
        rpp->p_time = 0; /* 还没有开始运行，所以 CPU 的滴答数为 0 */

        /*
         * make duplicate entries
         * where needed
         */

        /* 复制文件句柄 */
        for(rip = &u.u_ofile[0]; rip < &u.u_ofile[NOFILE];)
                if((rpp = *rip++) != NULL)
                        /* 由于子进程继承父进程打开的文件句柄
                         * 所以计数器要加 1 */
                        rpp->f_count++;
        if((rpp=up->p_textp) != NULL) {
                /* 因为和父进程共享，所以计数器都加 1 */
                rpp->x_count++;
                rpp->x_ccount++;
        }
        u.u_cdir->i_count++;
        /*
         * Partially simulate the environment
         * of the new process so that when it is actually
         * created (by copying) it will look right.
         */
        savu(u.u_rsav);
        rpp = p;
        /* 这里是暂时把父进程的 u_procp 切换到子进程上
         * 让子进程的数据虽是父进程的拷贝，却又有属于自己的 */
        u.u_procp = rpp;
        rip = up;
        n = rip->p_size; /* 这里获得父进程的内存大小，后面分配需要 */
        a1 = rip->p_addr;
        rpp->p_size = n;
        /* 为子进程分配和父进程相同大小的空间 */
        a2 = malloc(coremap, n);
        /*
         * If there is not enough core for the
         * new process, swap out the current process to generate the
         * copy.
         */
        /* 处理空间不够的情况 */
        if(a2 == NULL) {
                rip->p_stat = SIDL; /* 设置进程状态为还在生成中
                                     * 防止被执行 */
                rpp->p_addr = a1;
                savu(u.u_ssav);
                /* 把父进程的数据换出到交换空间中 */
                xswap(rpp, 0, 0);
                rpp->p_flag =| SSWAP;
                rip->p_stat = SRUN;
        } else {
        /*
         * There is core, so just copy.
         */
                rpp->p_addr = a2;
                while(n--)
                        copyseg(a1++, a2++);
        }
        u.u_procp = rip;
        return(0);
}

3.6. 进程调度

调度算法

swtch 函数实现进程的调度算法：

  • 选出标记为 SRUN 状态、p_flag 为 SLOAD 的进程
  • 拥有最高执行优先级，即 p_pri 值最小的进程

关键算法的代码如下： 

/* 遍历 proc，选出优先级最高的 */
i = NPROC;
do {
        rp++;
        if(rp >= &proc[NPROC])
                rp = &proc[0];
        /* 必须是可执行的进程 */
        if(rp->p_stat==SRUN && (rp->p_flag&SLOAD)!=0) {
                /* 选出最小 p_pri 的 */
                if(rp->p_pri < n) {
                        p = rp;
                        n = rp->p_pri;
                }
        }
} while(--i);

休眠和唤醒：

  • 让当前进程进入休眠状态：sleep
  • 唤醒进程：wakeup

3.7. 交换处理

交换处理用来处理使用内存资源时，内存不够的情况。

sched 函数用来交换处理对象的进程，在 main 函数创建 proc[0] 后，就开始调用，所以 proc[0] 也可以叫做调度进程。

sched 主要就是遍历 proc[0]，寻找可换出/换入的进程，如果换入时调用 malloc 分配空间存在内存不足时，就再遍历 proc，找出可换出的进程并换出，然后再次换入新进程；如果都失败，就休眠，直到收到中断后，再从 proc 遍历寻找。sched 函数实现如下： 

sched()
{
        struct proc *p1;
        register struct proc *rp;
        register a, n;

        /*
         * find user to swap in
         * of users ready, select one out longest
         */

        goto loop;

sloop:
        /* 不存在换出对象，就进入休眠状态，直到被中断 */
        runin++;
        sleep(&runin, PSWP);

loop:
        /* 设置中断优先级为 6，防止被中断 */
        spl6();
        n = -1;
        for(rp = &proc[0]; rp < &proc[NPROC]; rp++)
                /* 寻找运行时间最长的进程，如果进程是运行中，并且不是 SLOAD */
                if(rp->p_stat==SRUN && (rp->p_flag&SLOAD)==0 &&  /* rp->p_flag&SLOAD 等价于 !SLOAD */
                   rp->p_time > n) {
                        p1 = rp;
                        n = rp->p_time;
        }
        /* 没有找到就设置 runout，然后进入休眠状态
         * 直到被中断后继续寻找 */
        if(n == -1) {
                runout++;
                sleep(&runout, PSWP);
                goto loop;
        }

        /*
         * see if there is core for that process
         */

        spl0();
        rp = p1;
        a = rp->p_size;
        /* 如果换入的进程在代码段中不存在
         * 表示代码段也需要换入 */
        if((rp=rp->p_textp) != NULL)
                if(rp->x_ccount == 0)
                        a =+ rp->x_size;
        /* 为代码段分配内存 */
        if((a=malloc(coremap, a)) != NULL)
                goto found2;

        /*
         * none found,
         * look around for easy core
         */

        /* 处理内存不足的情况 */
        spl6();
        /* 如果内存不够，就把不重要的进程给换出了
         * 既找出：存在内存中（SLOAD）、不是系统进程（SSYS）、
         * 不是被锁的进程（SLOCK）、处于睡眠状态（SWAIT）或者处于停止
         * 状态（SSTOP）*/
        for(rp = &proc[0]; rp < &proc[NPROC]; rp++)
        if((rp->p_flag&(SSYS|SLOCK|SLOAD))==SLOAD &&
            (rp->p_stat == SWAIT || rp->p_stat==SSTOP))
                /* 如果找到就跳到 found1 */
                goto found1;

        /*
         * no easy core,
         * if this process is deserving,
         * look around for
         * oldest process in core
         */

        /* 换出进程距离上次不能小于 3 秒，小于 3 秒表示太频繁
         * 跳到 sloop 继续休眠 */
        if(n < 3)
                goto sloop;
        /* 设置 n 为 -1，再来寻找运行时间过长，可换出的进程 */
        n = -1;
        for(rp = &proc[0]; rp < &proc[NPROC]; rp++)
        if((rp->p_flag&(SSYS|SLOCK|SLOAD))==SLOAD &&
           (rp->p_stat==SRUN || rp->p_stat==SSLEEP) &&
            rp->p_time > n) {
                p1 = rp;
                n = rp->p_time;
        }
        /* 距上次换出时间小于 2 秒，又阻塞 */
        if(n < 2)
                goto sloop;
        rp = p1;

        /*
         * swap user out
         */

found1:
        spl0();
        /* 清除状态位（SLOAD），执行换出处理 */
        rp->p_flag =& ~SLOAD;
        /* 第二个 2 参数为 1，表示从内存中释放进程 */
        xswap(rp, 1, 0);
        goto loop;

        /*
         * swap user in
         */

found2:
        /* found2 是执行换入处理 */
        if((rp=p1->p_textp) != NULL) {
                if(rp->x_ccount == 0) {
                        if(swap(rp->x_daddr, a, rp->x_size, B_READ))
                                goto swaper;
                        rp->x_caddr = a;
                        a =+ rp->x_size;
                }
                rp->x_ccount++;
        }
        rp = p1;
        if(swap(rp->p_addr, a, rp->p_size, B_READ))
                goto swaper;
        mfree(swapmap, (rp->p_size+7)/8, rp->p_addr);
        rp->p_addr = a;
        /* 设置标志位为 SLOAD */
        rp->p_flag =| SLOAD;
        /* 设置新的运行时间 */
        rp->p_time = 0;
        goto loop;

swaper:
        panic("swap error");
}

数据段和代码段分别用 xswap 和 xalloc 函数用来完成交换工作。 

xswap(p, ff, os)
int *p;
{
        register *rp, a;

        rp = p;
        /* 如果被换出的长度为 0，表示要换出整个进程的数据段
         * 为啥不为这个参数定义个宏呢，感觉可读性不好啊
         */
        if(os == 0)
                os = rp->p_size;
        /* 分配交换空间 */
        a = malloc(swapmap, (rp->p_size+7)/8);
        if(a == NULL)
                panic("out of swap space");
        /* 递减代码段的计数器 */
        xccdec(rp->p_textp);
        /* 设置进程为调度锁 */
        rp->p_flag =| SLOCK;
        /* 执行换出 */
        if(swap(a, rp->p_addr, os, 0))
                panic("swap error");
        /* 如果 ff 为 1，表示要释放内存 */
        if(ff)
                mfree(coremap, os, rp->p_addr);
        /* 把数据段的地址设置成交换空间的地址 */
        rp->p_addr = a;
        /* 清除标志位 */
        rp->p_flag =& ~(SLOAD|SLOCK);
        /* 重新设置运行时间 */
        rp->p_time = 0;
        /* 重置 runout */
        if(runout) {
                runout = 0;
                wakeup(&runout);
        }
}

xalloc(ip)
int *ip;
{
        register struct text *xp;
        register *rp, ts;

        /* u_agr[1]为 exec 执行时设置的代码段长度
         * 长度为 0 不做任何处理 */
        if(u.u_arg[1] == 0)
                return;
        rp = NULL;
        /* 遍历 text[]，如果代码段已经存在 text[] 里，x_count 递增 */
        for(xp = &text[0]; xp < &text[NTEXT]; xp++)
                if(xp->x_iptr == NULL) {
                        if(rp == NULL)
                                rp = xp;
                } else
                        if(xp->x_iptr == ip) {
                                xp->x_count++;
                                u.u_procp->p_textp = xp;
                                goto out;
                        }
        if((xp=rp) == NULL)
                panic("out of text");
        /* 代码段初始化 */
        /* 引用计数加 1 */
        xp->x_count = 1;
        xp->x_ccount = 0;
        xp->x_iptr = ip;
        ts = ((u.u_arg[1]+63)>>6) & 01777;
        xp->x_size = ts;
        /* 为代码段分配交换空间 */
        if((xp->x_daddr = malloc(swapmap, (ts+7)/8)) == NULL)
                panic("out of swap space");
        expand(USIZE+ts);
        estabur(0, ts, 0, 0);
        u.u_count = u.u_arg[1];
        /* 程序执行头 */
        u.u_offset[1] = 020;
        u.u_base = 0;
        readi(ip);
        rp = u.u_procp;
        rp->p_flag =| SLOCK;
        /* 换出数据 */
        swap(xp->x_daddr, rp->p_addr+USIZE, ts, 0);
        rp->p_flag =& ~SLOCK;
        rp->p_textp = xp;
        rp = ip;
        rp->i_flag =| ITEXT;
        rp->i_count++;
        expand(USIZE);

out:
        /* 如果没有任何内存中进程引用代码数据，就换出 */
        if(xp->x_ccount == 0) {
                savu(u.u_rsav);
                savu(u.u_ssav);
                xswap(u.u_procp, 1, 0);
                u.u_procp->p_flag =| SSWAP;
                swtch();
                /* no return */
        }
        xp->x_ccount++;
}

4. panic

当内核无法正常工作时，就调用 panic 函数： 

panic(s)
char *s;
{
        panicstr = s;
        update();
        printf("panic: %s\n", s);
        for(;;)
                idle();
}

painc 主要是死循环中不断调用 idle。idle 函数实现如下： 

.globl  _idle
_idle:
        mov     PS,-(sp)
        spl     0
        wait
        mov     (sp)+,PS
        rts     pc

主要设置处理器优先级为 0，表示响应所有优先级的中断，然后调用 wait 等待被中断。

5. 内存管理

内存使用情况统一用 map 结构来管理： 

struct map
{
        char *m_size; /* 未使用地址的大小 */
        char *m_addr; /* 未使用空间的地址 */
};

交换空间和物理内存，都是用 map 结构来记录，分别使用了两个数组： 

int     coremap[CMAPSIZ];       /* space for core allocation */
int     swapmap[SMAPSIZ];       /* space for swap allocation */

CMAPSIZ 和 SMAPSIZ 定义如下： 

#define CMAPSIZ 100             /* size of core allocation area */
#define SMAPSIZ 100             /* size of swap allocation area */

调用 malloc 分配内存。malloc 用了 First Fit 算法，传递 coremap 或 swapmap 进去，找到最先匹配到合适的空间，然后分配空间，并调整大小： 

malloc(mp, size)
struct map *mp;
{
        register int a;
        register struct map *bp;

        for (bp = mp; bp->m_size; bp++) {
                /* 找出最先匹配大小的空间 */
                if (bp->m_size >= size) {
                        a = bp->m_addr;
                        /* 调整未分配空间的位置 */
                        bp->m_addr =+ size;
                        /* 调整大小 */
                        if ((bp->m_size =- size) == 0)
                                /* 如果分配的空间刚好是需要的空间
                                 * 就左移元素*/
                                do {
                                        bp++;
                                        (bp-1)->m_addr = bp->m_addr;
                                } while ((bp-1)->m_size = bp->m_size);
                        return(a);
                }
        }
        return(0);
}

这里说明 swap 和内存空间是用同一种算法来管理的。

释放空间调用的 mfree 函数： 

/*
 * Free the previously allocated space aa
 * of size units into the specified map.
 * Sort aa into map and combine on
 * one or both ends if possible.
 * 参数 aa 是要释放的地址
 */
mfree(mp, size, aa)
struct map *mp;
{
        register struct map *bp;
        register int t;
        register int a;

        a = aa;
        /* 遍历 coremap 或 swapmap，一直让 bp 指向要释放的地址 */
        for (bp = mp; bp->m_addr<=a && bp->m_size!=0; bp++);
        /* 移动位置 */
        if (bp>mp && (bp-1)->m_addr+(bp-1)->m_size == a) {
                /* 调整大小 */
                (bp-1)->m_size =+ size;
                if (a+size == bp->m_addr) {
                        (bp-1)->m_size =+ bp->m_size;
                        while (bp->m_size) {
                                bp++;
                                (bp-1)->m_addr = bp->m_addr;
                                (bp-1)->m_size = bp->m_size;
                        }
                }
        } else {
                if (a+size == bp->m_addr && bp->m_size) {
                        bp->m_addr =- size;
                        bp->m_size =+ size;
                } else if (size) do {
                        t = bp->m_addr;
                        bp->m_addr = a;
                        a = t;
                        t = bp->m_size;
                        bp->m_size = size;
                        bp++;
                } while (size = t);
        }
}

6. 中断处理

周边硬件设备主动发出中断信号，然后进程被暂停，调用中断处理函数。如果没有中断处理，进程就必须不断轮询去检查设备情况。

V6 包含以下中断：

  • 块设备处理
  • 终端输入
  • 时钟中断

陷入：来自 CPU 内部发出的信号，当出现如除以 0 错误的时候，CPU 会发出陷入事件并调用相应的处理函数（这样就不用内核去主动检测了）。

6.1. 处理器优先级和中断优先级

PSW 中处理器优先级大于等于当前的中断优先级，则不处理，直到优先级下降。

处理器优先级为 0～7，如下： 

.globl  _spl0, _spl1, _spl4, _spl5, _spl6, _spl7
_spl0:
        spl     0
        rts     pc

_spl1:
        spl     1
        rts     pc

_spl4:
        spl     4
        rts     pc

_spl5:
        spl     5
        rts     pc

_spl6:
        spl     6
        rts     pc

_spl7:
        spl     HIGH  / HIGH的值实质上为 6
        rts     pc

7. 管道

管道的优点是低投入，高产出，只用分配固定的大小即可实现进程之间的通信，比起用中间的文件方式会更加省硬盘资源，比如： 

a1 > tmp

a2 < tmp

这样会分配 a1 产出数据大小的空间。相比之下管道效率更好，占用资源更少。